package base.sort;

public class MergeSort {

    /**
     * 合并方法
     * @param arr
     * @param low
     * @param mid
     * @param high
     */
    public static void merge(int[] arr, int low, int mid, int high) {
        if(low >= high) return;
        int[] tmpArr = new int[high - low +1];
        int i = low, j = mid + 1;
        int tmpIndex = 0;
        while (i <= mid && j <= high) {
            if(arr[i] <= arr[j]) {
                tmpArr[tmpIndex] = arr[i];
                tmpIndex ++;
                i ++;
            }else {
                tmpArr[tmpIndex] = arr[j];
                tmpIndex ++;
                j ++;
            }
        }
        while (i <= mid) {
            tmpArr[tmpIndex] = arr[i];
            tmpIndex ++;
            i ++;
        }
        while (j <= high) {
            tmpArr[tmpIndex] = arr[j];
            tmpIndex ++;
            j ++;
        }
        for (int k = 0; k < tmpArr.length; k++)
            arr[low + k] = tmpArr[k];
    }

    /**
     * 归并排序
     * @param arr
     * @param start
     * @param end
     */
    public static void mergeSort(int[] arr, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        mergeSort(arr,start,mid);
        mergeSort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }

    public static void main(String[] args) {
        int[] a = {2,3,50,33,-1,22,19};
        mergeSort(a,0,a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
}
